import java.util.Comparator;

/**
 * This is an implementation of a heap that is backed by an array.
 *
 * This implementation will accept a comparator object that can be used to
 * define an ordering of the items contained in this heap, other than the
 * objects' default compareTo method (if they are comparable). This is useful if
 * you wanted to sort strings by their length rather than their lexicographic
 * ordering. That's just one example.
 *
 * Null should be treated as positive infinity if no comparator is provided. If
 * a comparator is provided, you should let it handle nulls, which means it
 * could possibly throw a NullPointerException, which in this case would be
 * fine.
 *
 * If a comparator is provided that should always be what you use to compare
 * objects. If no comparator is provided you may assume the objects are
 * Comparable and cast them to type Comparable<T> for comparisons. If they
 * happen to not be Comparable you do not need to handle anything, and you can
 * just let your cast throw a ClassCastException.
 *
 * This is a minimum heap, so the smallest item should always be at the root.
 *
 * @param <T>
 *            The type of objects in this heap
 */
public class BinaryHeap<T> implements Heap<T>
{
    /**
     * The comparator that should be used to order the elements in this heap
     */
    private Comparator<T> comp;

    /**
     * The backing array of this heap
     */
    private T[] data;

    /**
     * The number of elements that have been added to this heap, this is NOT the
     * same as data.length
     */
    private int size;
    private int nextPointer;

    /**
     * Default constructor, this should initialize data to a default size (11 is
     * normally a good choice)
     *
     * This assumes that the generic objects are Comparable, you will need to
     * cast them when comparing since there are no bounds on the generic
     * parameter
     */
    public BinaryHeap()
    {
        this.data = (T[])new Object[11];
        this.nextPointer = 1;
    }

    /**
     * Constructor that accepts a comparator to use with this heap. Also
     * initializes data to a default size.
     *
     * When a comparator is provided it should be preferred over the objects'
     * compareTo method
     *
     * If the comparator given is null you should attempt to cast the objects to
     * Comparable as if a comparator were not given
     *
     * @param comp
     */
    public BinaryHeap(Comparator<T> comp)
    {
        this.comp = comp;
        this.data = (T[])new Object[11];
        this.nextPointer = 1;
        this.size++;
    }

    @Override
    public void add(T item)
    {
        //resize
        if(this.nextPointer >= this.data.length)
        {
            T[] oldData = this.data;
            int newLength = this.data.length*2 +1;
            this.data = (T[])new Object[newLength];

            for(int i = 1; i<oldData.length; i++)
            {
                this.data[i] = oldData[i];
            }
        }
        this.data[this.nextPointer] = item;
        this.checkAndFlipUp(this.nextPointer);
        this.nextPointer++;
        this.size++;
    }

    @Override
    public boolean isEmpty()
    {

        return (this.size == 0);
    }

    @Override
    public T peek()
    {
        return this.data[1];
    }

    @Override
    public T remove()
    {
        //get what was at the end of the list
        T oldNode = this.data[1];
        T replacement = this.data[this.size];
        this.data[1] = replacement;
        this.data[this.size] = null;

        this.checkAndFlipDown(1);
        this.size--;
        this.nextPointer--;
        return oldNode;
    }

    @Override
    public int size()
    {
        return this.size;
    }

    private void checkAndFlipUp(int index)
    {
        if(index == 1)
        {
            return;
        }

       //get the parent index of this node
        int parentIndex;
        //if index is even
        if(index%2 == 0)
        {
            parentIndex = index/2;
        }
        else
        {
            parentIndex = (index-1)/2;
        }

        T child = this.data[index];
        T parent = this.data[parentIndex];

        //if a comparator is not provided
        if(this.comp == null)
        {
            //cast to comparable and do the compare that way.
            if(child==null)
            {
                //flip
                this.data[parentIndex] = child;
                this.data[index] = parent;
                this.checkAndFlipUp(parentIndex);
            }
            else if(Comparable.class.cast(child).compareTo(Comparable.class.cast(parent))<0)
            {
                //flip
                this.data[parentIndex] = child;
                this.data[index] = parent;
                this.checkAndFlipUp(parentIndex);
            }
            else
            {
                return;
            }
        }
        else
        {
            //if child is less than parent
            if(this.comp.compare(child, parent)<0)
            {
                //flip
                this.data[parentIndex] = child;
                this.data[index] = parent;
                this.checkAndFlipUp(parentIndex);
            }
            else
            {
                return;
            }
        }
    }

    private void checkAndFlipDown(int index)
    {
        //get the indeces of children
        int leftIndex = index*2;
        int rightIndex = (index*2) + 1;
        int minIndex;

        //check one of the children is outside the list
        if (rightIndex > this.size())
        {
            if (leftIndex > this.size)
            {
                return;
            }
            else
            {
                minIndex = leftIndex;
            }
        }

        //set min to whichever child is lower
        else
        {
            T left = this.data[leftIndex];
            T right = this.data[rightIndex];
            //if a comparator is not provided
            if(this.comp == null)
            {

                if(left == null)
                {
                    minIndex = rightIndex;
                }
                else if(right == null)
                {
                    minIndex = leftIndex;
                }
                //cast to comparable and do the compare that way.
                else if( Comparable.class.cast(left).compareTo(Comparable.class.cast(right))<=0)
                {
                    minIndex = leftIndex;
                }
                else
                {
                    minIndex = rightIndex;
                }
            }
            else
            {
                //if left is less than right
                if(this.comp.compare(left, right)<=0)
                {
                    minIndex = leftIndex;
                }
                else
                {
                    minIndex = rightIndex;
                }
            }
        }

        //Flip if node > min
        T node = data[index];
        T min = data[minIndex];

        //if a comparator is not provided
        if(this.comp == null)
        {
            if(node == null)
            {
                data[minIndex]=node;
                data[index]=min;
                this.checkAndFlipDown(minIndex);
            }
            if(min == null)
            {
                return;
            }

            //cast to comparable and do the compare that way.
            else if( Comparable.class.cast(node).compareTo(Comparable.class.cast(min))>0)
            {
                data[minIndex]=node;
                data[index]=min;
                this.checkAndFlipDown(minIndex);
            }
        }
        //if a comparator is provided
        else
        {
            //if min is less than node
            if(this.comp.compare(node, min)>0)
            {
                data[minIndex]=node;
                data[index]=min;
                this.checkAndFlipDown(minIndex);
            }
        }
    }


}
